package top.minuy.algorithm.sort.merge;
/**
 * @author Minuy
 * @time 23:25
 * @date 2021/8/28
 */
public class MergeBuSort {
    private MergeBuSort(){}

    public static <E extends Comparable<E>> void sort(E[] arr){
        Object[] temp = new Object[arr.length];

        int size = 1;
        while (size < arr.length) {
            for (int i = 0; i+size < arr.length; i+=(size*2)) {
                int mid = size+i;

//                for(int kk = 0;kk<arr.length;kk++){
//                    System.out.print(arr[kk]+" ");
//                }
//                System.out.println(" mid = "+mid);

                if(arr[mid-1].compareTo(arr[mid])>0 && i!=mid) {
                    // [i,mid),[mid,i+size)
                    int l = i+(size*2);
                    if(l>arr.length){
                        l = arr.length;
                    }
                    merge(arr, i, mid, l,temp);
                }else {
//                    System.out.println(" 不调用");
                }
//                System.out.println();
//                System.out.println();
            }
            size*=2;
//            System.out.println("size = "+size);
//            System.out.println();
        }
    }

    /**
     * 合并有序区间[l,m),[m,r)
     * @param arr 数组
     * @param l 开始索引
     * @param m 中间索引
     * @param r 结束索引
     * @param temp 内存优化
     * @param <E> 必须能比较
     */
    private static <E extends Comparable<E>> void merge(E[] arr, int l, int m, int r,Object[] temp) {
        for (int i=l;i<r;i++){
            temp[i] = arr[i];
        }

        int IL = l,IR = m;

        for (int i = l;i<r;i++){
            if(IL>=m){
                // 左边越界，直接复制右边
                arr[i] = (E)temp[IR];
                // System.out.print(arr[i]+"|");
                IR++;
            }else if(IR >= r){
                // 右边越界，直接复制左边
                arr[i] = (E)temp[IL];
                // System.out.print(arr[i]+"|");
                IL++;
            }else if(((E)temp[IL]).compareTo((E)temp[IR])<0){
                // 左边小，复制左边
                arr[i] = (E)temp[IL];
                // System.out.print(arr[i]+"|");
                IL++;
            }else {
                // 右边小，复制右边
                arr[i] = (E)temp[IR];
                // System.out.print(arr[i]+"|");
                IR++;
            }
            // System.out.print("|");
        }

//        for (int i=l;i<r;i++){
//            temp[i] = arr[i];
//            System.out.print(temp[i]+" ");
//        }
//        System.out.println(" 调用"+" l = "+l+" mid = "+m+" r = "+r);
    }

}
